题干
https://leetcode-cn.com/problems/valid-parentheses/
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

思路
这种匹配的题目并且跟顺序相关的，应该可以反应到用栈的数据结构来处理。
代码实现比较丑，并且额外使用了两个set去存储，空间复杂度更高一些。
* 时间复杂度：O(n)，其中 n 是字符串 s 的长度。
* 空间复杂度：O(n+∣Σ∣*2)，其中 Σ 表示字符集，本题中字符串只包含6种括号，∣Σ∣=6
* 栈中的字符数量为O(n)，而哈希表使用的空间为O(∣Σ∣)，还额外使用了2个set，使用的空间也为∣Σ∣=6，相加即可得到总空间复杂度

public class IsValidBracket20 {
    public static boolean isValid(String s) {
        if (s == null || s.length() < 2) {
            return false;
        }

        // 存储
        Map<Character, Character> init = new HashMap();
        init.put('(', ')');
        init.put('[', ']');
        init.put('{', '}');

        Set<Character> left = new HashSet<>();
        left.add('(');
        left.add('[');
        left.add('{');

        Set<Character> right = new HashSet<>();
        right.add(')');
        right.add(']');
        right.add('}');

        Stack<Character> stack = new Stack<>();

        int size = s.length();
        if (size%2 == 1) {
            return false;
        }

        for (int i = 0; i < size; i++) {
            char c = s.charAt(i);
            // 左括号全部入栈
            if (left.contains(c)) {
                stack.push(s.charAt(i));
            }
            // 右括号两种判断：栈空和栈非空
            if (right.contains(c) && stack.isEmpty()) {
                return false;
            }
            if (right.contains(c) && !stack.isEmpty()
                    && c != init.get(stack.pop())) {
                return false;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String s = "()))";
        boolean res = isValid(s);
        System.out.println("res = " + res);
    }
}

官方题解
* 时间复杂度：O(n)，其中 n 是字符串 s 的长度。
* 空间复杂度：O(n+∣Σ∣)，其中 Σ 表示字符集，本题中字符串只包含6种括号，∣Σ∣=6
* 栈中的字符数量为O(n)，而哈希表使用的空间为O(∣Σ∣)，相加即可得到总空间复杂度
public boolean isValid1(String s) {
    if (s == null || s.length() < 2) {
        return false;
    }

    // 存储三组
    Map<Character, Character> init = new HashMap();
    init.put(')', '(');
    init.put(']', '[');
    init.put('}', '{');
    int size = s.length();
    if (size%2 == 1) {
        return false;
    }
    Deque<Character> stack = new LinkedList<Character>();
    for (int i = 0; i < size; i++) {
        char c = s.charAt(i);
        // 右括号是key，左括号全部入栈。遇到右括号判断是不是栈顶与之匹配
        if (init.containsKey(c)) {
            if (!stack.isEmpty()
                    && c != init.get(stack.peek())) {
                return false;
            }
            // 如果相等，则需要将栈顶元素弹出
            stack.pop();
        } else {
            stack.push(c);
        }
    }
    return stack.isEmpty();
}
